package com.njupt.LinkTable;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 142. 环形链表 II
 */
public class DetectCycle {

    /**
     * 暴力解，以空间换时间
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
       Map<ListNode, Integer> map = new HashMap<>();
       int count = 0;
       ListNode p = head;
       while(p != null){
           if(map.containsKey(p)){
               return p;
           }else {
               map.put(p,count++);
               p = p.next;
           }
       }

        return null;
    }

    /**
     *
     * @param head
     * @return
     */
    public Boolean detectCycle1(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }

        return false;

    }

    public static void main(String[] args) {

        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);

        head.next = node1; node1.next = node2;node2.next = node3; node3.next = node1;

        DetectCycle test = new DetectCycle();
        System.out.println(test.detectCycle(head).val);
    }
}
